/*
 * @lc app=leetcode.cn id=3 lang=typescript
 *
 * [3] 无重复字符的最长子串
 */

// @lc code=start

//  思路：滑动窗口
//  参考：https://labuladong.github.io/algo/2/19/51/

//  复杂度：O(n) O(n)

function lengthOfLongestSubstring(s: string): number {
    const window: Map<string, number> = new Map()
    let left = 0, right = 0, res = 0
    while (right < s.length) {
        const c = s[right]
        right++
        // 进行窗口内数据的一系列更新
        window.set(c, window.has(c) ? window.get(c)! + 1 : 1)
        // 判断左侧窗口是否要收缩
        while (window.get(c)! > 1) {
            const d = s[left]
            left++
            // 进行窗口内数据的一系列更新
            window.set(d, window.get(d)! - 1)
        }
        res = Math.max(res, right - left)
    }
    return res
};
// @lc code=end

console.log(lengthOfLongestSubstring('abcabcbb')) // 3
console.log(lengthOfLongestSubstring('bbbbb'))    // 1
console.log(lengthOfLongestSubstring('pwwkew'))   // 3

// 也可以使用set

// function lengthOfLongestSubstring(s: string): number {
//     const set = new Set()
//     let right = 0, res = 0
//     for (let i = 0; i < s.length; i++) {
//         if (i != 0) {
//             set.delete(s.charAt(i - 1))
//         }
//         while (right < s.length && !set.has(s.charAt(right))) {
//             set.add(s.charAt(right))
//             right++
//         }
//         res = Math.max(res, set.size)
//     }
//     return res
// };